package com.shm.leetcode;

import java.util.*;

/**
 * 290. 单词规律
 * 给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
 *
 * 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
 *
 * 示例1:
 *
 * 输入: pattern = "abba", str = "dog cat cat dog"
 * 输出: true
 * 示例 2:
 *
 * 输入:pattern = "abba", str = "dog cat cat fish"
 * 输出: false
 * 示例 3:
 *
 * 输入: pattern = "aaaa", str = "dog cat cat dog"
 * 输出: false
 * 示例 4:
 *
 * 输入: pattern = "abba", str = "dog dog dog dog"
 * 输出: false
 * 说明:
 * 你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
 * @author SHM
 */
public class WordPattern {
    /**
     * 执行结果：
     * 解答错误
     * 显示详情
     * 输入：
     * "abba"
     * "dog dog dog dog"
     * 输出：
     * true
     * 预期结果：
     * false
     * @param pattern
     * @param s
     * @return
     */
    public boolean wordPattern(String pattern, String s) {
        String[] ss = s.split(" ");
        char[] patterns = pattern.toCharArray();
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i=0;i<patterns.length;i++) {
            List<Integer> list = map.getOrDefault(patterns[i], new ArrayList<>());
            list.add(i);
            map.put(patterns[i],list);
        }
        Set<Map.Entry<Character, List<Integer>>> entries = map.entrySet();
        for (Map.Entry<Character, List<Integer>> entry : entries) {
            List<Integer> value = entry.getValue();
            for (int i = 1; i < value.size(); i++) {
                if (!ss[value.get(i)].equals(ss[value.get(i-1)])){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 方法一：哈希表
     * 思路及解法
     *
     * 在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。
     *
     * 想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。
     *
     * 在实际代码中，我们枚举 \textit{pattern}pattern 中的每一个字符，利用双指针来均摊线性地找到该字符在 \textit{str}str 中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。
     *
     * 思路及解法
     *
     * 时间复杂度：O(n + m)O(n+m)，其中 nn 为 \textit{pattern}pattern 的长度，mm 为 \textit{str}str 的长度。插入和查询哈希表的均摊时间复杂度均为 O(n + m)O(n+m)。每一个字符至多只被遍历一次。
     * 空间复杂度：O(n + m)O(n+m)，其中 nn 为 \textit{pattern}pattern 的长度，mm 为 \textit{str}str 的长度。最坏情况下，我们需要存储 \textit{pattern}pattern 中的每一个字符和 \textit{str}str 中的每一个字符串。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/word-pattern/solution/dan-ci-gui-lu-by-leetcode-solution-6vqv/
     * @param pattern
     * @param s
     * @return
     */
    public boolean wordPattern_2(String pattern, String s) {
        char[] patterns = pattern.toCharArray();
        Map<String,Character> s2c = new HashMap<>();
        Map<Character,String> c2s = new HashMap<>();
        int length = s.length();
        int k =0;
        for (int i = 0; i < patterns.length; i++) {
            if (k>=length){
                return false;
            }
            int p = k;
            while (p<length&&s.charAt(p)!=' '){
                p++;
            }
            String str = s.substring(k, p);
            if (s2c.containsKey(str)&&s2c.get(str)!=patterns[i]){
                return false;
            }
            if (c2s.containsKey(patterns[i])&&!c2s.get(patterns[i]).equals(str)){
                return false;
            }
            s2c.put(str,patterns[i]);
            c2s.put(patterns[i],str);
            k=p+1;
        }
        return k>=length;
    }
}
